ABC049 D - 連結

提出

code: python

n, k, l = map(int, input().split())

road = [[] for _ in range(n)]

rail = [[] for _ in range(n)]

for i in pq:

for i in rs:

class UnionFind:

def __init__(self, n):

# 木の高さを格納する（初期状態では0）

# 人間の数

# 検索

def find(self, x):

# 根ならその番号を返す

return x

# 根でないなら、親の要素で再検索

else:

# 走査していく過程で親を書き換える(return xが代入される)

# 併合

def union(self, x, y):

# 根を探す

x = self.find(x)

y = self.find(y)

if x == y:

return

# 木の高さを比較し、低いほうから高いほうに辺を張る

else:

# 木の高さが同じなら片方を1増やす

# 同じ集合に属するか判定

def same(self, x, y):

return self.find(x) == self.find(y)

UF = UnionFind(n)

解答

code: python

from collections import Counter

n, k, l = map(int, input().split())

# print(pq)

# print(rs)

class UnionFind:

def __init__(self, n):

def root(self, x):

return x

else:

def union(self, x, y):

x = self.root(x)

y = self.root(y)

if x == y:

return

else:

def same(self, x, y):

return self.root(x) == self.root(y)

uf1 = UnionFind(n + 1)

for p, q in pq:

uf1.union(p, q)

uf2 = UnionFind(n + 1)

for r, s in rs:

uf2.union(r, s)

res = []

# 各都市ごとに「根」を求めて、その根に付随する都市の個数を答える

# 都市 a,b が「道路のみ」でも「鉄道のみ」でも行き来できる

# -> uf1.root(a) == uf1.root(b) かつ uf2.root(a) == uf2.root(b)

for i in range(1, n + 1):

res.append((uf1.root(i), uf2.root(i)))

# print(res)

c = Counter(res)

# print(c)

# Counter({(1, 2): 2, (1, 1): 1, (1, 4): 1})

for r in res:

テーマ

メモ

提出

code: python

n, k, l = map(int, input().split())

# print(pq)

# print(rs)

class UnionFind:

def __init__(self, n):

def find(self, x):

return x

else:

def union(self, x, y):

x = self.find(x)

y = self.find(y)

if x == y:

return

else:

def same(self, x, y):

return self.find(x) == self.find(y)

ufk = UnionFind(k)

for p, q in pq:

ufk.union(p, q)

ufl = UnionFind(l)

for r, s in rs:

ufl.union(r, s)

for i in range(n):

pass